package com.lw.leetcode.other.b;

import java.util.*;

/**
 * 6279. 数组乘积中的不同质因数数目
 */
public class DistinctPrimeFactors {

    public static void main(String[] args) {

        // 输入：nums = [2,4,3,7,10,6]
        //输出：4
        //解释：
        //nums 中所有元素的乘积是：2 * 4 * 3 * 7 * 10 * 6 = 10080 = 25 * 32 * 5 * 7 。
        //共有 4 个不同的质因数，所以返回 4 。
        //示例 2：
        //
        //输入：nums = [2,4,8,16]
        //输出：1
        //
        //来源：力扣（LeetCode）
        //链接：https://leetcode.cn/problems/distinct-prime-factors-of-product-of-array
        //著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

        // 4
//        int[] arr = {2, 4, 3, 7, 10, 6};

        // 1
        int[] arr = {2, 4, 8, 16};

        DistinctPrimeFactors test = new DistinctPrimeFactors();
        int i = test.distinctPrimeFactors(arr);
        System.out.println(i);

    }

    public int distinctPrimeFactors(int[] nums) {
        Arrays.sort(nums);
        int item = 0;
        Set<Integer> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            if (num == item) {
                continue;
            }
            item = num;
            find(num, list);
            set.addAll(list);
            list.clear();
        }
        return set.size();
    }

    private void find(int t, List<Integer> list) {
        int l = (int) Math.pow(t, 0.5);
        while (t != 0) {
            boolean f = true;
            for (int i = 2; i <= l; i++) {
                if (t % i == 0) {
                    list.add(i);
                    t /= i;
                    f = false;
                    break;
                }
            }
            if (f) {
                if (t > 1) {
                    list.add(t);
                }
                break;
            }
        }
    }

}
